/** 回文子串 ---有多少个回文子串【连续】
给你一个字符串 s ，请你统计并返回这个字符串中 **回文子串** 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
 */

/**
 * dp[i][j] i~j范围内是否是回文串
 * cbabc
 * 需要res记录过程
 * s[i]==s[j] 是回文数 && |i-j|<=1
 * dp[i][j]=true res++
 * 【遍历顺序】 依赖dp[i+1][j-1]。 所以从左下角开始遍历，保证都被计算过
 *  i倒序 m-1~0
 *  j正序 i～m;
 */

var countSubstrings = function(s) {
  const m = s.length;
  const dp = Array(m).fill().map(() => Array(m).fill(false));
  let res=0;
  for(let i=m-1;i>=0;i--) { //从下到上
    for(let j=i;j<m;j++) { //从左到右
      if(s[j]==s[i] && (Math.abs(i-j)<2 || dp[i+1][j-1])) {
        dp[i][j]=true;
        res++;
      }
    }
  }
  return res;
};
// const s = "abc";
const s = "aaa"; //6
console.log('回文子串',countSubstrings(s)) //3